package cn.algorithms_4ed.algo.sort;

/**
 * 快速排序
 * <p/>
 * User: erhu
 * Date: 13-6-16
 * Time: 上午10:59
 */
public class Quick extends Sort {
    @Override
    Sort sort() {
        sort(0, data.length - 1);
        return this;
    }

    private void sort(int low, int high) {
        // 优化：数组变小时，切换到插入排序；
        if (high > low) {
            int j = partition(low, high);
            sort(low, j - 1);
            sort(j + 1, high);
        }
    }

    private int partition(int low, int high) {
        int i = low;
        int j = high;

        Comparable v = data[low];
        while (true) {
            while (less(data[++i], v))
                if (i == high)
                    break;

            while (less(v, data[--j]))
                if (j == low)
                    break;

            if (i >= j)
                break;
        }
        exchange(low, j);
        return j;
    }

    /**
     * main
     */
    public static void main(String[] args) {
        Quick quick = new Quick();
        quick.sort().show();
    }
}
